package com.clstu.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 46题,全排列
 */
public class Solution2 {

    public List<List<Integer>> permute(int[] nums) {
        int len = nums.length;
        // 使用一个动态数组保存所有可能的全排列
        List<List<Integer>> res = new ArrayList<>();
        //先判断是否用得着全排列
        if (len == 0) {
            return res;
        }
        boolean[] used = new boolean[len];
        List<Integer> path = new ArrayList<>();
        dfs(nums, len, 0, path, used, res);
        return res;
    }

    private void dfs(int[] nums, int len, int depth, List<Integer> path, boolean[] used, List<List<Integer>> res) {
        //如果到底,说明找到了一种排列,加入到结果集合中
        if (depth == len) {
            res.add(new ArrayList<>(path));//创建对象才能有对象
            return;
        }
        // 在非叶子结点处，产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然得通过一个循环实现。
        for (int i = 0; i < len; i++) {
            //如果没有固定这个点,就把它固定了接着向下递归
            if (!used[i]) {
                path.add(nums[i]);
                used[i] = true;
                dfs(nums, len, depth + 1, path, used, res);
                // 注意：下面这两行代码发生 「回溯」，回溯发生在从 深层结点 回到 浅层结点 的过程，代码在形式上和递归之前是对称的
                //将它重新置为false,在下一轮确定的时候第一个确定的就是第i个元素
                used[i] = false;
                path.remove(path.size() - 1);//每一轮循环完之后path一定是空的(最外层为空,内层不为空)
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        Solution2 solution = new Solution2();
        List<List<Integer>> lists = solution.permute(nums);
        lists.add(new ArrayList<>());
        lists.add(new ArrayList<>());
        lists.add(new ArrayList<>());
        lists.sort(new SizeComparator());
        System.out.println(lists);
    }
    //比较器
    public static class SizeComparator implements Comparator<List>{

        @Override
        public int compare(List o1, List o2) {
            return o2.size() - o1.size();
        }
    }
}
